#pragma once
#include <utility>
#include <vector>
#include <iostream>
#include <string>
#include <cassert>
using namespace std;

template<class K>
struct HashDefault
{
  size_t operator()(const K& key)
  {
    return (size_t)key;
  }
};

template<>
struct HashDefault<string>
{
  size_t operator()(const string& key)
  {
    //BKDR Hash
    size_t hash=0;
    for(auto ch:key)
    {
      hash+=hash*131+ch;
    }
    return hash;
  }  
};

template<class T>
struct DataNode
{
  DataNode(const T& data)
    :_next(nullptr)
    ,_data(data)
  {}
  DataNode<T>* _next;
  T _data;
};


template<class K,class T,class KeyOfT,class HashFunc>
class HashBucket;

template<class K,class T,class KeyOfT,class HashFunc>
class __HBIterator
{
  typedef DataNode<T> Node;
  typedef __HBIterator<K,T,KeyOfT,HashFunc> Self;
public:
  Node* _node;
  HashBucket<K,T,KeyOfT,HashFunc>* _pht;

  __HBIterator(Node* node,HashBucket<K,T,KeyOfT,HashFunc>* pht)
  :_node(node)
  ,_pht(pht)
  {}

  Self& operator++()//返回迭代器类型，简化为Self
  {
    assert(_node);//_node==nullptr,此时++断言错误
    //迭代器如何++？
    //1._node->_next不为nullptr，则_node=_node->_next 
    //2.否则计算当前位置，将迭代器指向下一个不为空的桶的初始位置
    if(_node->_next)
    {
      _node=_node->_next;
    }
    else 
    {
      KeyOfT kot;
      HashFunc hf;

      size_t hashi=hf(kot(_node->_data))%_pht->_table.size();
      ++hashi;
      while(hashi<_pht->_table.size() && _pht->_table[hashi]==nullptr)
      {
        ++hashi;
      }
      if(hashi<_pht->_table.size())//找到了
      {
        _node=_pht->_table[hashi];
      }
      else 
      {
        _node=nullptr;
      }

      return *this;
    }
  }

  T& operator*()
  {
    return _node->_data;
  }

  T* operator->()
  {
    return &_node->_data;
  }
  
  bool operator==(const Self& s)const
  {
    return _node==s._node;
  }

  bool operator!=(const Self& s)const 
  {
    return _node!=s._node;
  }
  
  
};

template<class K,class T,class KeyOfT,class HashFunc>
class HashBucket
{
  typedef DataNode<T> Node;
  template<class KF,class TF,class KeyOfTF,class HashFuncF> 
  friend class __HBIterator;
  
public:
  typedef __HBIterator<K, T, KeyOfT, HashFunc> iterator;

  iterator begin()
  {
    for(size_t i=0;i<_table.size();++i)
    {
      if(_table[i])
      {
        return iterator(_table[i],this);
      }
    }
    return end();
  }

  iterator end()
  {
    return iterator(nullptr,this);
  }
  //析构函数

  pair<iterator,bool> insert(const T& data)
  {
    KeyOfT kot;
    HashFunc hf;

    //插入新元素,但是不能插入重复元素->find
    iterator pos=find(kot(data));
    if(pos!=end())
    {
      return make_pair(pos,false);
    }

    size_t oldSize=_table.size();
    if(_n==oldSize)
    {
      size_t newSize=oldSize==0?10:oldSize*2;
      vector<Node*> newTable;
      newTable.resize(newSize);
      for(size_t i=0;i<oldSize;++i)
      {
        Node* cur=_table[i];
        while(cur)
        {
          Node* next=cur->_next;
          size_t hashi=hf(kot(cur->_data))%newSize;
          cur->_next=newTable[hashi];
          newTable[hashi]=cur;
          cur=next;
        }
        _table[i]=nullptr;
      }
      _table.swap(newTable);
    }
    Node* newNode=new Node(data);
    size_t hashi=hf(kot(data))%_table.size();
    newNode->_next=_table[hashi];
    _table[hashi]=newNode;

    ++_n;

    return make_pair(iterator(newNode,this),true);
  }

  iterator find(const K& key)
  {
    if(_table.size()==0)
    {
      return iterator(nullptr,this);
    }

    KeyOfT kot;
    HashFunc hf;
    size_t hashi=hf(key)%_table.size();
    Node* cur=_table[hashi];
    while(cur)
    {
      if(kot(cur->_data)==key)
      {
        return iterator(cur,this);
      }
      cur=cur->_next;
    }
    return iterator(nullptr,this);
  }

  bool erase(const K& key)
  {
    KeyOfT kot;
    HashFunc hf;
    size_t hashi=hf(key)%_table.size();
    Node* cur=_table[hashi];
    Node* prev=nullptr;
    while(cur)
    {
      if(kot(cur->_data)==key)
      {
        //进行删除，判断是否头删
        if(!prev)
          _table[hashi]=cur->_next;
        else 
          prev->_next=cur->_next;
        delete cur;
        return true;
      }
      else 
      {
        prev=cur;
        cur=cur->_next;

      }
    }
    return false;
  }

  void printMap()//for debug
  {
    string str="";
    for(int i=0;i<_table.size();++i)
    {
      cout<<str<<i<<endl;
      Node* cur=_table[i];
      while(cur)
      {
        cout<<str<<cur->_data.first<<":"<<cur->_data.second<<endl;
        cur=cur->_next;
      }
      str+="\t";
    }
  }
  void printSet()//for debug
  {
    string str="";
    for(int i=0;i<_table.size();++i)
    {
      cout<<str<<i<<endl;
      Node* cur=_table[i];
      while(cur)
      {
        cout<<str<<cur->_data<<endl;
        cur=cur->_next;
      }
      str+="\t";
    }
  }
private:
  vector<Node*> _table;
  size_t _n=0;
  
};
